
//小和问题
public class Solution {
    public static void main(String[] arg){
        int[] arr = new int[]{1,3,4,2,5};
        int res = process(arr, 0, arr.length - 1);
        System.out.println(res);
    }

    public static int process(int[] arr, int L, int R) {
        if(L >= R){
            return 0;
        }
        int mid = L + ((R - L) >> 1);

        return  process(arr, L, mid) +
                process(arr, mid + 1, R) +
                merage(arr, L, R, mid);
    }

    private static int merage(int[] arr, int L, int R, int mid) {
        int i = L;
        int j = mid + 1;
        int k = 0;
        int res = 0;
        int[] extra = new int[R - L + 1];

        while(i <= mid && j <= R){
            res += arr[i] < arr[j] ? (R - j + 1) * arr[i] : 0;
            extra[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
        }
        while(i <= mid){
            extra[k++] = arr[i++];
        }
        while(j <= R){
            extra[k++] = arr[j++];
        }
        for (int t = 0; t < extra.length; t++) {
            arr[L + t] = extra[t];
        }
        return res;
    }

}